package com.jhy.review.huiyi;

import java.util.Arrays;

/**
 * @author go_jhy
 * @create 2022/6/11 - 下午 5:23
 * 改版的快速排序
 * 1、0  每次排好一个数 分为两个部分
 * 2.0   每次排好一些数 分为三个部分
 * 3.0   用随机数 来和最后一个数交换 这样就算出来一个数学期望
 * n*logn  空间复杂度是 logn-->最差的情况n  左右中 好的情况是logn级别。实际的数学期望
 *  最后收敛到logn的水平。
 *
 */
@SuppressWarnings("all")
public class Code06_QuickSort {


    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;

    }


    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);

    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            //先定义一个随机的数 和最后一个数进行交换 那么现在最后一个数就是分区的关键。
            swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            //分区partition 定义前一次分区后的左右两边的位置
            int[] partition = partition(arr, l, r);
            //递归
            quickSort(arr, l, partition[0] - 1);
            quickSort(arr, partition[1] + 1, r);

        }

    }

    public static int[] partition(int[] arr, int l, int r) {
        //先定义左右两边那个访问
        int less = l - 1;
        //因为最后一个所以右边那个访问就是从最后一个开始
        int more = r;
        //如果l下标大于或者等于的时候就停止
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr, less++, l++);
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }
        //分层成功后 就是左边全是小于r的 中间是等于r的 右边是大于r的 然后交换最后一个数 是more的第一个数 也就是当前的数
        swap(arr, more, r);
        //最后放回分区中间的范围
        return new int[]{less + 1, more};
    }


    public static void main(String[] args) {
        int[] arr = {5, 7, 6, 4, 3, 5};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}